package LeetCode;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName interview
 * @Description: TODO
 * @date ${DAT}16:13
 */
public class LeetCode279 {
    /*
    *解法*
    进行图的建模：
    整个问题转化为一个图论问题
    从n到0，每个数字表示一个节点
    如果两个数字x到y相差一个完全平方数，则连接一条边
    我们得到了一个无权图
    原问题转化成，求这个无权图中从N到0的最短路径
     */


    /**
     * 动态规划
     * @param n
     * @return
     */
//    public int numSquares(int n) {
//        int[] dp = new int[n + 1];
//        for (int i = 1; i <= n; i++){
//            dp[i] = i;//这是设置初始的状态 就是每个数字都可以是i个1相加
//            for (int j = 1; i - j * j >= 0; j++){
//                dp[i] = Math.min(dp[i],dp[i - j * j] + 1);//动态转移方程
//            }
//        }
//        return dp[n];
//    }
    public int numSquares(int n) {
        int[] dp = new int[n + 1];//0~12
        for (int i = 1; i <= n; i++){
            dp[i] = i;
            for (int j = 1; i - j * j >= 0; j++){
                dp[i] = Math.min(dp[i],dp[i - j * j] + 1);
            }
        }
        return dp[n];
    }
}
